# Full text of "mit :: lcs :: tr :: MIT-LCS-TR-212"

## See other formats

m MIT/LCS/TR-212 Digitalized Signatures and Public Key Functions as Intractable as Factorization Michael C. Rabin This blank page was inserted to preserve pagination. MIT/LCS/TR-212 DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION Michael 0. Rabin January 1979 MASSACHUSETTS INSTITUTE OF TECHNOLOGY LABORATORY FOR COMPUTER SCIENCE CAMBRIDGE MASSACHUSETTS 02139 This empty page was substituted for a blank page in the original document. DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION by Michael 0. Rabin Visiting Professor of Applied Mathematics, MIT Professor of Mathematics, Hebrew University Jerusalem, Israel ABSTRACT . We introduce a new class of public-key functions involving a number n = p-q having two large prime factors. As usual, the key n is public, while p and q are the private key used by the issuer for production of signatures and function inversion. These functions can be used for all the applications involving public-key functions proposed by Diffie and Hellman [2], including digitalized signatures. We prove that for any given n, if we can invert the function y = E n (x) for even a small percentage of the values y then we can factor n . Thus as long as factorization of large numbers remains practically intractable, for appropriatly chosen keys not even a small percentage of signatures are forgerable. Breaking the RSA function [6] is at most as hard as factorization , but is not known to be equivalent to factorization even in the weak sense that ability to invert all function values entails -2- ablllty to factor the key. Computation time for these functions, I.e. signature verification, is several hundred times faster than for the RSA scheme in [6]. Inversion time, using the private key, is comparable. The almost-everywhere Intractability of signature-forgery for our functions (on the assumption that factoring 1s intractable) is of great practical significance and seems to be the first proved result of this kind. Key words. Public-key functions, D1g1tal1zed signatures, Factorization, Intractable problems. -3- INTRODUCTION In their fundamental paper [2] Diffie and Hellman have shown how public key trap door functions can be employed for the solution of various problems arising in electronic mail, including the production of digital ized signatures. An example of a public- key function usable for digitalized signatures was given in the elegant paper [6 ] by Rivest, Adelman, and Shamir, who introduced a trap-door one-way function employing a number n factorable into a product n = p-q of two large primes. The decoding algorithm given in [6] for this function requires knowledge of the factors p, q of n. It is, however, conceivable that another decoding algorithm exists that does not involve or imply factorization of n. Thus, breaking this one-way function is at most as difficult as factorization, but possibly easier. We present a different public key function which can be used for digitalized signatures, and all the other applications, in the same way as the above- mentioned function. The function in [6J is 1-1. Our function is four to one, but this causes only slight modifications in the applications. -4- For this new function we can prove that the ability to forge signatures or decode messages 1s equivalent to the ability to factor large numbers. In fact, for any given n , a signature forgery or inversion algorithm effective in just a small percentage of all cases, say one case in a thousand, already leads to a factorization of n . By Inversion we mean finding for a number y in the range of E one of the x such that E(x) ■ y. In view of the present-day Intractability of the factorization problem, this fact lends substantial support to the viability of our public-key function. As long as it 1s Impossible in practice to factor large numbers, 1t will be Impossible for a fixed key to forge signatures even for a small percentage of all messages. The fact that we are able to prove, on the assumption that factoring is hard, that for our function, for a fixed key n whose factorization 1s not given, Inversion must be hard for almost all messages 1s of great significance. For other trap door functions 1t may be the case that even though worst case complexity or even average complexity are high, in say one percent of cases Inversion 1s -5- easy. From a commercial point of view this would pose an unacceptable risk. For example, an adversary can randomly search by computer for messages useful to him, such as payment instructions, on which he can forge signatures. To the best of our knowledge, we have in this article the first example of an almost everywhere difficult problem of this type. In addition, computation time for this function is several hundred times faster, and inversion when p,q are known, is about eight tlmesrfaster than the corresponding algorithms in [6]. If we Invert the RSA function by Chinese Remaindering, as we do here, then inversion time for the two functions are comparable. Theorems 1 and 2 concerning the equivalence of square-root extraction with factorization, are perhaps also of independent number-theoretic interest. 1 . THE PUBLIC-KEY FUNCTION Let n = p-q be the product of two large primes p,q, and let < b < n. DEFINITION 1: The function E p b (x) is defined for < x < n by E .(x) = x(x+b) mod n, < E n b (x)<n. Computation of E(x), for fixed n,b, requires one addition, one multiplication, and one division of -6- x(x+b) by n to find the residue E b (x). Note that only the public key n,b, but not the factorization n = p-q, is required for encoding. 2. INVERSION ALGORITHMS Given c = x(x+b) modn, we want to find the four values < x. < n, 1 o < 4 such that Mx^) - c, We assume of course that the private key, i.e. the factors of n , are known. Throughout this paper res(A.B) will denote the residue of A when divided by B, and (A,B) will denote the greatest common divisor (g.c.d.) of A and B. The decoder, who is the issuer of the public key n,b, knows the factorization n = p*q. Clearly, it sufficies to solve the equation x(x+b) =c separately mod p and mod q and then find a solution mod n . Let a be an integer so that a = I mod p , a = mod q , and b satisfy b = 1 mod q, b = mod p . If r and s satisfy the congruence mod p and mod q respectively, then z = ar + bs solves the congruence mod n , and x = res (z,nj is the sought-after solution. -7- In what follows let p be a fixed prime. We shall understand all integers a to be residues mod p, i.e., 0' <_ a < p . For d a quadratic residue (q.r.) modp, /a will denote any one of the two integers such that (/3) = mod p , and - /d will denote p - /d. To solve (1) f(x) = x + bx - c = mod p 2 2 let d ■ b/2 mod p then (x+d) = c + d mod p , x = - d t /c+d . We can solve the equation (1) as soon as we can extract square roots modp, i.e., 2 solve y - m = mod p . Assume first that p = 4k - 1 so that 4|(p+l). Since m is a q.r., m 5 1 mod p. Weclaimthat (2) i - j/m = m mod p is one of the two square roots of m. Namely, l z = m = m«m = m mod p . Thus one implementation of the function would use p and q such that p = q = 3 mod 4, and the decoding algorithm (2). For p =■ 4k + 1 we directly solve the equation (1) by a probabilistic algorithm. This is a special case of Berlekamp's root-finding 1n 6F(p) algorithm given in [1]. -8- The short proof given here is taken from [5], where generalizations to GF(p n ) appear. If the roots of (1) are a, Be GF(p) then x 2 + b x - c = (x - a) (x - 3) The roots in GF(p) of the polynomial equation x -1=0 are exactly the quadratic residues aeGF(p). Consequently, if a is a quadratic residue while 3 is not, then (x - 1, f(x)) = x - a, so that a and subsequently 3 = -(b+a) mod p are readily found. Assume that a and 3 are of the same type , i.e., both quadratic residues (q.r.) or both quadratic non-resi- dues mod p, and that aj*3- Let < 6 < p then a + 5 and 3+6 are of the same type if and only if (a+6)/(3+6) is a q.r. mod p. As 6 takes all values £ 6 < p except 6 = -3, the quotient (a+6)/(B+6) takes all values <_ y < P except y = 1 . Thus for exactly ^— choices 6, a+6 and 3+o will not be of the same type. Since f(x-6) = (x-ot-6) (x-a-3) » we have that for a Jiandom choice of < 6 < p, with probability 1/2 (3) (x c -1, f(x-6)) = x-a-6 or x-3-6. Thus on the average two values of 6 have to be tried for finding the roots of (1). The computation of the g.c.d. (3) requires O(logap) operations in GF(p), i.e., additions and multiplications -9- mod p. Namely, by essentially repeated squarlngs start- ing with x, compute x + h = res(x z , f(x-6)). Whenever a quadratic polynomial is encountered, divide by f(x-6) to produce a linear polynomial. Note that x is a formal variable so that all computations involve just pairs of residues mod p. Now by (3) , x + h - 1 is x - o - 6 or x - 3 - 6 , so that -6 - h + 1 is a root of (1). 3. USE IN SIGNATURES To employ E for signatures the signer P produces two large primes p,q by use of one of the prime-testing algorithms [3,7]. He forms n ■ p«q, chooses a number < b < n and publicizes the pair (n,b) (but not the factors p.q). By convention, when wishing to sign a given message, M,P adds as suffix a word U of an agreed upon length k. The choice of U 1s randomized each time a message is to be signed. The signer now compresses Mi * MU by a hash- ing function to a word C(Mi) = c, so that as a binary number c < n; see [4]. The computation of C( ) is publicly known, so that c - C(Mi) is checkable by everybody. P now checks whether for this c the congruence (4) x(x+b) = c mod n -10- 1s solvable. By the analysis of Section 2, this congruence 1s solvable if and only if m = c + d 2 is a q.r. mod p and mod q. Thus testing the solvability of (4) amounts to computing the Jacobi Symbols (^) and (-J) which is essentially a g.c.d. type computation. If congruence (4) is not solvable then P picks another random Ui and tries Ci ■ C(MUi). The expected number of tries is 4. When for some U the congruence (4) 1s solvable for c ■ C(MU), P finds a solution x. DEFINITION 2 : For a given public key n,b used by P and an agreed upon compressing function C( ) and Integer k, P's signature on a message M 1s a pair U,x where fc(U) = k and x(x + b) = C(MU) mod n. Anybody can check P's signature by computing c = C(MU) and testing whether x(x+b) = c mod n. The randomization of the suffix U of M also adds protection against possible attacks on the function E. Without the suffix, an adversary may attempt to feed to P messages M for his signature, hoping to learn the factorization of n from the solution of x(x+b) = C(M) mod n ,which will be produced by P as his signature. Actually, this does not seem a serious threat because of the hashing effected by C(M). -11- However, the randomized suffix of length k leads to essentially 2 possible random values for c = C(MU). Thus for, say, k = 60, the adversary has no effective control over the congruence (4) that P will solve. 4. INVERSION IS EQUIVALENT TO FACTORIZATION We now want to show that 1f an adversary can invert E n . (x) by any algorithm then he can factor n. By invert- ing we mean finding for y one of the four x such that E n b^ = y * F"t nd1 ng one such x 1s sufficient for the would be signature forger, so that we want to show that this is hard. Thus the problem of, say, forging P's signilUFtl 1* exactly as intractable as the factorization of a number n which 1s a product of large primes. As mentioned in the Introduction, the scheme 1n [6] 1s at mo4t as safe as factorization but conceivably easier to crack. In the following theorem we count an addition of num- bers a,b, <_ n as one operation. It is readily seen that 1f we can solve (4) for fixed n,b and arbitrary c then we can extract square roots, i.e., solve y 2 = m mod n whenever a solution exists. Namely, letting b = 2d mod n(n 1s odd) and m » c + d 2 mod n, (4) turns into -12- x 2 + 2dx + d 2 = (x+d) 2 = m mod n. Thus our result follows from THEOREM 1 : Let AL be an algorithm for finding one of the solutions of (5) y 2 = m mod n whenever a solution exists, and requiring F(n) steps. There exists an algorithm for factoring n requiring 2F(n) + 21og 2 n steps. Vn.ooi. Assume that n - p*q 1s a product of two primes, the case relevant for E n b . The proof easily extends to the general case. For any < k < n, (k,n) - 1, there are exactly four solutions for the congruence y 2 = k 2 mod n. Namely, let res(k.p) = r, res(k.q) = s then the solutions y of this congruence satisfy res(y.p) = *r mod p.res(y.q) ■ = ±s mod q and each of the four sign combinations gives rise to a different solution. Defining for < yi,y 2 < n,yi*y 2 to mean y? = y| mod n, we see that this equivalence relation decomposes the set < y < n, (y,n) ■ 1 into classes each containing four elements. Denote by /m the solution of (5) by AL for any m, (m,n) =1. If AL produces more than one solution then -13- the factorization algorithm that follows is even further facil itated . Choose at random a number < k < n. If (k,n) + 1 then we directly get a factor of n. In practice, this possibility can be neglected. Compute k 2 = m mod n. Compute k! = /m by AL . Now, k is i n the equi val ence class, by the relation a,, of k x . In a random choice of < k < n, all four possible choices of numbers within any class are equally likely. Hence with probability 1/2 or k = ki mod p, k = - ki mod q k = - ki mod p, k = ki mod q Therefore with probability 1/2 (6) (k-ki ,n) = p or q The computation of /m requires F(n) steps. The computation of the g.c.d. (6) requires at most log 2 n subtractions and divisions by 2, of numbers smaller than n, Hence the expected number of steps is 2F(n) + 2 log 2 n. If we count bit-operations then subtraction of numbers smaller than n requires at most log 2 n bit-operations and the bound is 2F(n) + 2(log 2 n) 2 . The previous theorem may be strengthened to cover the situation that for the given key E n b can be decoded in just a small percentage of all cases. -14- THSOREM 2 : If AL solves (5) in F(n) steps for 1/e of the < m < n, . (m.n) * V, for which (5) has a solution, then there is an algorithm for factoring n requiring 2eF(n) + 21og 2 n steps. Vfiooi. As in the proof of Theorem 1, choose a < k < n at random and compute k 2 = m mod n. Apply AL to find ,/m. If the computation runs more than F(n) steps abort it and choose another k. Whenever a root k a - /m is found, compute (k-ki.n). The analysis in the proof of Theorem 1 implies that with probability 1/2 each such try produces a factorization of n. The expected number of choices of k leading to a /m is § »nd the expected number of 4ucce**(M of AL needed for a factorization, is 2. Thus the total expected number of steps is 2eF(n) + 21og 2 n. Note that we embark on the second phase of the factorization only after a success of AL in finding /m. If for example e = 1000, and F(n) were not prohibi- tively large, then an adversary, could factor n in 2000 F(n) + 21og 2 n steps. Consequently, if no practical algorithm for factoring n is possible , then no practical decoding algorithm could work in even 1/1000 of all cases. -15- GENERALIZATIONS The above method of construction of a one-way function can be extended to employ polynomials or powers of x of small degrees other than 2. Assume for example that n = p*q, where p and q are primes of the form 3k + l . The one-way function will be E(x) = x 3 mod n. The decoding 1s effected by solving x 3 - m e mod p and mod q by a probabilistic algorithm similar to the one used 1n Section 2. Again one can prove that any algorithm for extracting cubic roots leads, for n of the above form, to a factorization of n. The probability that x 3 = w mod n 1s solvable for a random w 1s 1/9. Thus for utilization ' In signatures the quadratic scheme seems best. -16- REFERENCES [1] Berlekamp, E.R., Factoring polynomials over large finite fields, Math, of Coop., vol. 24 (1970), pp. 713-735. [2] Diffie, W. , and Hellman, M. , New directions in crypto- graphy, IEEE Trans, of Inf. Theory, IT-22, (November 1976), pp. 644-654. [3] Rabin, M. , O., Probabilistic algorithms, Algorithms and Complexity, Recent Results and New Directions, J. P. Traub, editor, Academic Press, New York, 1976, pp t 31*40, [4] Rabin,' M.O., Digitalized signatures, Foundations of Secure Computations, R. Lipton and R. DeMillo editors, Academic Press New York, 1978/ [5] Rabin, M.O., Probabilistic algorithms in finite fields, submitted for publication. [6] Rivest, R.L., Shamir A., and Adleman L. , A method for obtaining digital signatures and public-key crypto- sy 8 terns, Coram. ACM. vol. 21 (February 1978) . [7] Solovay, R. , and Strassen, V., A fast monte -carlo test for primality, SIAM Jour, on Comp. Vol. 6 (1977), pp. 84-85.